package linkList;

import java.util.HashMap;

import utils.linkListUtil;
import utils.linkListUtil.ListNode;
import utils.linkListUtil.Node;

public class copyRandomList {
    // 有一个map是多余的
    // 还有就是random中的val表示的是索引的位置
    public static Node copyRandomList(Node head) {
        if (head==null) {
            //返回一个新的节点
            return head;
        }
        if (head.next==null) {
            Node node = new Node(head.val);
            if (head.random!=null) {
                // random.val表示指向节点的索引位置
                node.random=node;
            }
            return node;
        }
        // 需要遍历两次，第一次处理next，第二次处理random
        HashMap<Node,Node> map = new HashMap<>();
        HashMap<Node,Node> map2 = new HashMap<>();
        Node next=head.next,curr=head,newHead=null,node1=null,node2=null;

        while (curr!=null) {
            map.put(curr, curr.random);
            if (node1==null&&node2==null) {
                node1 = new Node(curr.val);
                // 是第一次进来
                // 保存新的head
                newHead=node1;
            }
            map2.put(curr, node1);
            // 判断是否为null
            if (next!=null) {
                node2 = new Node(next.val);
            }else{
                node2=null;
            }
            
            node1.next=node2;
            curr=next;
            node1=node2;
            if (next==null) {
                break;
            }
            next=next.next;
        }
        curr=head;
        node1=newHead;
        Node random=null;

        while (curr!=null) {
            random = map.get(curr);
            Node rnode = map2.get(random);
            node1.random=rnode;
            curr=curr.next;
            node1=node1.next;
        }
        return newHead;

    }
    public static void main(String[] args) {
        int[] l1 = new int[] { 7, 13,11,10,1 };
        Node list1 = linkListUtil.createLinkedListByNode(l1);
        Node mergeTwoLists = copyRandomList(list1);
        while (mergeTwoLists != null) {
            System.out.println(mergeTwoLists.val);
            mergeTwoLists = mergeTwoLists.next;
        }
    }
}
